This invention relates to the field of modeling interactions among entities having geometry, specifically for interference and collision detection and distance computation. Note that the following discussion refers to a number of publications by author(s) and year of publication, and that due to recent publication dates certain publications are not to be considered as prior art vis-à-vis the present invention. Discussion of such publications herein is given for more complete background and is not to be construed as an admission that such publications are prior art for patentability determination purposes.
A recurrent problem in computer-based simulations of geometric volumes is determining the clearances between volumes. Many applications, including robotics and visualization, require modeling of interactions of objects to facilitate users in motion planning, control of automation, graphical programming, motion-preview, virtual reality and dynamic simulation. In robotics, for example, this modeling permits detection of possible collisions between a robot and obstacles within its environment, or another robot. Both accuracy and efficiency are needed. Accuracy is needed because inaccurate determination of clearances could lead to physical collisions. Efficiency is needed because, in the real-time computational context of robotics, information about clearances is required while the robot and elements of the environment are in motion. The determination should also be conservative, so as not to miss the closest approach of two volumes.
Early methods for clearance determination did not provide distance information for clearances among volumes. See, e.g., Fuchs et al., “On Visible Surface Generation by a priori Tree Structures,” Proc. of ACM SIGGRAPH, pages 124-133, 1980. Later methods addressed this problem but did not handle swept-body distance or swept-body interference detection. See, e.g., Sato et al., “Efficient Collision Detection Using Fast Distance Calculation Algorithms for Convex and Non-convex Objects,” Proc. 1996 IEEE Int'l Conf on Robotics and Automation, pages 771-778, Minneapolis, Min., April 1996; Gottschalk et al., “OBB-tree: A Hierarchical Structure for Rapid Interference Detection,” Proc ACM SIGGRAPH'96, pages 171-180, August 1996. Further methods were able to handle swept volumes but did not provide clearance distance information for volumes that did not collide. See Canny, John, “Collision Detection for Moving Polyhedra,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 8(2):200-209, 1986; and Cameron, “Collision Detection by 4D Intersection Testing”, Intl Journal of Robotics Research, 6(3):291-302, June 1990.
These drawbacks were substantially addressed by the Applicant in U.S. Pat. No. 6,099,573, “Method and Apparatus for Modeling Interactions”; and U.S. Pat. No. 6,407,748, “Method and Apparatus for Modeling Interactions”. These advances are discussed in Xavier, Patrick, G., “Implicit Convex-Hull Distance of Finite-Screw-Swept Volumes”, 2002 IEEE International Conference on Robotics and Automation (ICRA) (May 2002). U.S. Pat. No. 6,099,573 describes a method for determining collisions and clearances, including distances, through calculations of bounding volumes based on unions of convex polygons and polyhedra. The above method, which computes an approximate minimum clearance between the volumes swept by two bodies under motion, was faster and more robust than the prior art.
U.S. Pat. No. 6,407,748 involved a complementary computation of clearances where two bodies were undergoing translation. This method computes the exact minimum clearance (to numerical precision limited by the representation of floating point numbers on the computer component of the invention) between the volumes swept by two bodies only undergoing translation.
Performance of applications such as robots and visualization is still limited by the computational efficiency of the clearance calculations. U.S. Pat. No. 6,099,573 and U.S. Pat. No. 6,407,748 both required explicit calculation of all the vertices of polyhedral approximations of the convex hulls of volumes swept by various nodes in the representations of the modeled objects. The present invention does not require explicit calculation of the vertices of polyhedral approximations of the convex hulls. Rather, the methods of the present invention provide more efficient computation of the clearance calculation by adapting an algorithm of Gilbert and Foo (Gilbert and Foo, “Computing the Distance Between General Convex Objects in Three—Dimensional Space”, IEEE Transactions on Robotics and Automation, Vol. 6, No. 1, February 1990, pages 53-61). The prior art was also limited by the kinds of the volumes that could be modeled. The present invention further permits use of a greater number of types of geometric primitives in modeling the volumes, including polyhedra, cones, cylinders and discs.
By avoiding computation of any explicit representations (exact or approximate) of the volumes swept by nodes of the modeled bodies, the present invention comprises a method that is faster than prior art, for the same accuracy. The hierarchical distance implementation of the present invention does not construct a swept bounding volume hierarchy (BVH) representation of either of the first or the second bodies.
The geometric representations of the bodies comprise unions of Convex Geometric Primitives (CGPs), including but not limited to convex polygons, convex polyhedra, closed discs, cones, cylinders, and spheres. From these CGPs, the BVH representations can be generated in pre-processing for each body. This can be done using various methods known to those skilled in the art. See for example, P. G. Xavier, “A Generic Algorithm for Construction Hierarchical Representations of Geometric Objects”, in Proceedings of the 1996 IEEE Intl Conf. on Robotics and Automation, pp. 3644-3651, Minneapolis, Minn., April 1996. A BVH is a tree whose nodes and leaves comprise CGPs.
An advance of the present invention is that it does not explicitly compute swept volumes. Instead, for a series of pairs of nodes, one node each from the respective BVHs, it determines the clearance between the convex hulls of the volumes “virtually swept” by the two nodes under the motions of their respective bodies. This makes the present invention more accurate than U.S. Pat. No. 6,099,573. Towards determining this clearance, the method determines for each of a series of direction vectors the furthest point “virtually swept” by a node, comprising one or more CGPs, over a period of time. To determine this clearance, embodiments of the present invention extend the algorithm of Gilbert and Foo for finding the minimum distance between two (stationary) convex geometric objects, by determining for each of a series of direction vectors, the location of the furthest point “virtually” swept by a node over a period of time, i.e. a node undergoing a motion.
Methods according to the present invention can utilize a representation (also referred to as a canonical representation) of a body in its canonical (“home”) position and orientation. The convex hull of a node from this representation that has been mapped to an arbitrary position and orientation can be compared to a direction vector (“w” vector) to locate the point on the convex hull that is furthest away, in the direction of the direction vector. This location which can be a vertex or point on the convex hull is referred to as the directionally furthest location (or vertex or point). Those skilled in the art will recognize that it is not necessary to construct a new BVH for the starting position of a body prior to each motion it may undergo.
The methods of the present invention can be applied to bodies undergoing motions including but not limited to translation, rotation, and translation concurrent with rotation, wherein motions can be described by time-dependent mappings. By determining an inverse mapping of the motion and applying the inverse mapping to the direction vector (w vector), then mapping the result to the original canonical representation of the body without actually sweeping out the volume according to the motion, the invention can determine the furthest point in the direction of the direction vector on the convex hull of the virtually swept volume generated by any given node of the BVH. The methods account for the swept volume due to the node and its body's motion over a period of time to determine the furthest point in a particular direction during the entire time period and locates this furthest point without performing the brute-force and computationally intensive calculation of an explicit representation of an approximate superset of the volume swept by the node over the period of time. Coordinated computations enable determination of the separation between the volumes virtually swept by pairs of nodes from the respective BVH representations. This provides a quick and reliably conservative determination of separation and/or collision detection of moving bodies over time to permit inter alia, collision avoidance.
Where a node comprises a convex polyhedron, the present invention determines the transition of the directionally furthest vertex to an edge-adjacent vertex on that polyhedron due to the motion of the direction vector under an inverse mapping (i.e. inverse time-dependent mapping). The determining of transitions from a vertex to an edge-adjacent vertex due to the motion of the direction vector under this mapping, is a unique aspect of the present invention.
Others have described trajectory calculations but do not provide the advance of the present invention. U.S. Pat. No. 5,537,119, “Method and System for Tracking Multiple Regional Objects by Multi-dimensional Relation”, provides a novel algorithm for detecting trajectory collisions, but the method involves tracks of objects that are not modeled with respect to volume. U.S. Pat. No. 6,285,805, “System and Method for Finding the Distance From a Moving Query Point to the Closest Point on One or More Convex or Non-convex Shapes”, involves a kind of calculation unrelated to the present invention. The method of U.S. Pat. No. 6,285,805 is appropriate for polygonal mesh-type models rather than the volume-based models of the present invention. U.S. Pat. No. 5,675,720, “Method of Searching for Points of Closest Approach, and Preprocessing Method Therefore” (Sato, et al.), also uses a mesh-type model and uses the original Gilbert algorithm directly. Moreover, although Sato's claims use the term “points of closest approach” in its Background and Description, it is clear that this term refers to the points of minimum distance between two objects at discrete (separated) points in time, rather than for the modeled objects across the entire time interval of their motion.
Another approach is to specialize the modeling of the volumes to a particular application domain, so that the collision-detection problem can be solved for a specific application rather than generally. An example of this approach is U.S. Pat. No. 6,577,925, “Apparatus and Method of Distributed Object Handling”. In this case, the volumes consist of “envelopes” that have been predetermined, based on known object geometry and trajectories, before the real-time computation to ensure non-collisions during subsequent movements along the predetermined trajectories. The clearance-detection computation can then use a brute-force algorithm rather than the more efficient algorithm of the present invention.
Other related work includes inventions for computer animation and virtual reality. Examples include U.S. Pat. No. 6,535,215, “Method for Animating 3-D Computer-Generated Characters”, and U.S. Pat. No. 6,054,991, “Method of Modeling Player Position and Movement in a Virtual Reality System”. While animation and VR need collision detection for modeled objects, in both of these cases the underlying representations differ from that of the present invention and hence lead to substantially different algorithms. The animation system, because it is not real-time, uses a brute-force algorithm for collision detection. The VR system, although real-time, does not have true 3-D representation of objects. Rather, it represents the objects in a series of planes, detecting 2-D collisions within the planes, again using a simpler brute-force approach.